(*
General discussion ( * )

We will now explain in depth the various constructs we have seen in action in the previous sample.

We start by showing how to define simple lists to store (finite) sequences of data.
We will show how we can manipulate the various elements of lists through pattern matching.
We will then show the large library of list operators such as List.map, List.filter and List.fold.
Finally we will see how we can generate lists with many elements, either with recursive functions, the List.init function or the powerful list comprehension syntax.
*)
module Chapter3Examples
  (*
  List Initialization ( * )

  We start with the construction of simple lists. This way we see how we can build the lists that we will use for subsequent computations.

  The type of a list is generic, and it depends on the type of its elements. A list of integers will have type
  int list (or List<int>)

  a list of strings will have type
  string list (or List<string>)

  and a list of generic elements of type 'a will have type
  a' list (or List<'a>).

  We define simple lists with a constant number of elements by listing those elements separated by a semicolon (";").
  The empty list has no elements, and is written as "[]".
  *)
  let empty = []
  let singleton = ["hello"]
  let sentence = ["Hello"; "world"; "I"; "love"; "the"; "smell"; "of"; "napalm"; "in"; "the"; "morning"]

  (*
  We can also create a list with the ( :: ) operator, which takes as input a value v and a list l and returns a list at which head is the value v followed by the elements of l.
  We could write the following instead of [1; 2; 3]:
  *)
  let explicit = 1 :: 2 :: 3 :: []

  (*
  We can create a list with all the integers in a certain range (including the extremes) by writing [l .. u] where l and u are the extremes.
  *)
  let range = [1..10]

  (*
  We can also write [l..s..u] to denote that the range elements will be distanced s; for example, [1..2..10] would contain only the elements [1; 3; 5; 7; 9].
  *)

  (*
  List Iteration ( * )

  We will now see how to analyze a list to extract its values and perform computations on them.

  Given a list we can do pattern matching on its structure with the same "match ... with" syntax we have seen in Chapter 1.
  A list can be matched against any valid shape it may have.
  The simplest shapes a list may have are simply two, the empty list and the list with at least an element x followed by the list xs:
  - []
  - x :: xs
  For example, we could find the first even element of a list with the function:
  *)
  let rec first_even l =
    match l with
    | [] -> failwith "no even elements"
    | x :: xs ->
      if x % 2 = 0 then x
      else first_even xs

  (*
  We could do more complicated forms of pattern matching, for example in the case of lists of lists.
  Let us consider the case of a function that, given a list of lists, checks if there is at least an empty list:
  *)
  let rec has_empty_element =
    function
    | []       -> false
    | [] :: xs -> true
    | x :: xs  -> has_empty_element xs

  (*
  We could even rebuild a modified list while traversing another.
  For example, we could remove all the odd elements or increment all the elements by one:
  *)
  let rec remove_odd =
    function
    | [] -> []
    | x :: xs ->
      if x % 2 = 0 then x :: (remove_odd xs)
      else remove_odd xs

  let rec add_one =
    function
    | [] -> []
    | x :: xs -> (x + 1) :: (add_one xs)

  (*
  A handy way to process all elements of a list sequentially is with a for-loop.
  We simply write "for x in l do BODY" where l is a list and we are set:
  *)
  let print_all l =
    for x in l do
      do System.Console.WriteLine(x.ToString())

  (*
  List Library ( ** )

  We can build a series of very general functions on lists that cover most of the things we are interested in doing.
  By building such a library, instead of rewriting the same list iteration patterns we have already seen in the four examples above (first_even, has_empty_element, remove_odd and add_one) we can focus on the actual logic of these functions and write just that.

  Let us build a generalized version of the add_one function in particular:
  *)

  let rec add_k k =
    function
    | [] -> []
    | x :: xs -> (x + k) :: (add_k k xs)

  let add_one' = add_k 1

  (*
  Functions such as add_k and add_one are all very similar: they iterate each element of the list, and then build a resulting list with each element of the original list transformed somehow.
  This pattern is called map:
  *)

  let rec map f =
    function
    | [] -> []
    | x :: xs -> (f x) :: (map f xs)

  (*
  We can use map now to define add_k very simply as:
  *)

  let add_k' k = map (fun x -> x + k)

  (*
  ( ** )
  [[[[ We could use partial specialization on the sum operator to achieve an even more elegant form: ]]]]
  *)
  let add_k'' k = map ((+) k)

  (*
  Functions such as remove_odd, on the other hand, are based on the idea of building a list with all the elements of another list that satisfy some criterion.
  This pattern is called filter:
  *)
  let rec filter p =
    function
    | [] -> []
    | x :: xs -> if p x then x :: filter p xs else filter p xs

  (*
  ( ** )
  [[[[ A note on generic types: both map and filter are generic functions, since they can work on lists of any type, provided that the parameters f and p are appropriate.
  In particular, f must be able to turn the elements of the list into something else, while p must be able to turn the elements of the list into a boolean value.
  The types of map and filter are generic, and are respectively:
  map : ('a -> 'b) -> 'a list -> 'b list
  filter : ('a -> bool) -> 'a list -> 'a list
   ]]]]
  *)

  (*
  The final pattern we see is a very general one, and it takes a list and performs some function on an accumulator and each element of the list in turn.

  Let us see an example of a function that uses an explicit accumulator to compute the sum of all the elements of a list:
  *)
  let sum l =
    let rec sum s =
      function
      | [] -> s
      | x :: xs -> sum (s+x) xs
    sum 0 l

  (*
  The idea is that we will generalize this function on the type and initial value of the accumulator s (in this case int and 0), the operation between s and each value of the list (in this case ( + )).
  The generalized pattern is:
  *)

  let rec fold s f =
    function
    | [] -> s
    | x :: xs -> fold (f s x) f xs

  let sum' = fold 0 (+)

  (*
  The fold function may appear complex at first, but we could rewrite it imperatively with the for construct, which is capable of iterating lists:
  *)

  let fold' s0 f l =
    let mutable s = s0
    for x in l do
      do s <- f s x
    s

  (*
  ( ** )
  [[[[
  This kind of list iteration is extremely common, and having captured it gives us great expressive power.
  Indeed, we could define both map and filter with fold (where @ is the concatenation operator, otherwise the resulting list would be reversed):
  ]]]]
  *)

  let map' f = fold [] (fun l x -> l @ [f x])
  let filter' p = fold [] (fun l x -> if p x then l @ [x] else l)

  (*
  The List module contains all the functions we have seen above plus many more such as zip, reduce, sum, etc.
  Be sure to try them to see all the things you can do with F# lists.
  *)

  (*
  List Comprehensions ( * )

  We now discuss a very powerful way to create, map and filter lists.

  List comprehensions allow us to define how the elements of a list are computed with a declarative piece of code.
  List comprehensions work as follows:
  - we write a piece of code inside square brackets
  - the piece of code is run
  - whenever the piece of code encounters the special instruction "yield x" for some x, it adds x to the list and keeps running
  Notice that the arguments of all yield instructions must have the same type, otherwise we will get a compiler error.
  We cannot build a list where the items do not all have the same type!

  A simple way to create a list with comprehensions could be a list of the sin/cos pairs sampled on the surface of a circle.
  The following list has type List<float * float>:
  *)

  let sincos_pairs =
    [
      for i = 0 to 100 do
        let a = (float i) / 100.0
        let theta = a * 2.0 * System.Math.PI
        yield cos theta,sin theta
    ]

  (*
  Let us say we wish to perform some conversion operator on a list, for example incrementing by one only those elements that are even.
  We use list comprehensions:
  *)
  let incr_even l =
    [
      for x in l do
        if x % 2 = 0 then yield (x+1)
    ]

  (*
  We could even build the map and filter functions with list comprehensions as follows:
  *)
  let map'' f l = [ for x in l do yield f x ]
  let filter'' p l = [ for x in l do if p x then yield x ]

  let map_filter f p l =
    [
      for x in l do
        if p x then yield f x
    ]

  (*
  Sequences ( ** )

  Lists are a way to manipulate finite sequences of values.
  Sequences, on the other hand, are a way to manipulate sequences of any kind, possibly even infinite.

  A sequence that contains a series of elements of type 'a will have type seq<'a>.
  We can generate a sequence from a list, with a generator or with the "init" and "initInfinite" functions:
  *)

  let range_seq = Seq.ofList range
  let range' =
    seq{
      for i = 1 to 100 do
        if i % 2 = 0 then
          yield i / 2, i * i
    }
  let range'' = Seq.init 10 (fun x -> x, x * x)
  let N = Seq.initInfinite (fun x -> x)

  (*
  Sequences are very similar to lists, but with an important difference: they are lazy.
  An infinite sequence such as N defined above is not executed immediately.
  Rather, the N sequence tries to maintain the knowledge of *how* to compute its elements, to be used when said elements are requested.
  We could print the first 10 natural numbers as follows:
  *)
  let print_10 =
    for x in Seq.take 10 N do
      do System.Console.WriteLine(x.ToString())


  (*
  Let us see how we can manipulate sequences to define the (infinite) sequence of prime numbers:
  *)
  let factors n =
    seq{
      for i = 2 to (n-1) do
        if n % i = 0 then yield i
    }

  let is_prime n =
    Seq.isEmpty (factors n)

  let primes =
    seq{
      for x in (Seq.skip 2 N) do
        if is_prime x then yield x
    }

  (*
  We can convert a sequence back to a list with the Seq.toList function, but beware: if the sequence is infinite the function will not terminate.

  Also, keep in mind that any library function in the List module such as map, zip, filter, fold can be found in the Seq module. So we could write:
  *)
  let evens = Seq.filter (fun x -> x % 2 = 0) N

  (*
  The various functions of the Seq module are lazy as sequences themselves, that is they do not compute the elements of the sequence right away, but rather they store the *way* these elements are computed so that they may find the elements when iterated.
  *)